package hash;

import java.util.NoSuchElementException;

/**
 * 基于开散列方案下的哈希表实现
 */
public class MyHashMap {

    private class Node{
        //对key求哈希运算
        int key;
        int value;
        Node next;//发生哈希碰撞时转链表就用next属性存储它的下一个节点

        public Node(int key, int value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
    //当前哈希表中实际存储元素的个数
    private int size;
    //默认哈希表的长度
    //也有的教科书将每个哈希表的数组元素称为哈希桶
    private static final int DEFAULT_CAPACITY=16;
    //默认负载因子
    private static final double LOAD_FACTOR=0.75;
    //取模数，用于取到key的索引
    private int M;
    //实际存储数据的数组：Node数组
    private Node[] data;
    public MyHashMap(){
        this(DEFAULT_CAPACITY);
    }
    public MyHashMap(int initCap) {
        this.data=new Node[initCap];//可以从外部传入
        this.M=initCap;//initCap:长度//对数组长度取模
    }
    public int hash(int key){//哈希方法
        return Math.abs(key)%M;//对key直接做绝对值对M取模
    }

    /**
     * 在当前哈希表中添加一个键值对 key=value
     * @param key
     * @param value
     */
    public int add(int key,int value){
        //1.先对key取模，得到存储的索引
        int index=hash(key);
        //2.遍历这个索引对应的链表，查看当前key是否已存在
        for(Node x=data[index];x!=null;x=x.next){//每个数组存储的时node节点，每个链表的链表头就存储在数组的索引位置
            if(x.key==key){
                //此时key已经存在，更新value
                int oldValue=x.value;
                x.value=value;
                return oldValue;
            }
        }
        //3.此时key对应的元素在当前哈希表中不存在，新建节点头插在哈希表中
//        Node head=data[index];//原先的头节点
//        Node node=new Node(key,value,head);//对于构造方法，新节点的next要等与head
        Node node=new Node(key,value,data[index]);
        data[index]=node;//最新的链表头要变为当前的node
        size++;
        //4.添加一个新元素后，查看是否需要扩容
        if(size/LOAD_FACTOR>= data.length){//元素个数/负载因子>=数组长度：此时我们认为冲突比较严重，需要进行扩容
            //size/LOAD_FACTOR>= data.length也可以写成LOAD_FACTOR* data.length<=size
            //TODO:哈希表的扩容
            resize();
        }
        return value;
    }

    /**
     * 哈希表扩容
     */
    private void resize() {
        //新数组的长度变为原来的一倍
        Node[] newData=new Node[data.length<<1];
        //细节：原节点的key对应新数组的索引hash有变化，现在的取模数应该变为新数组的长度（如之前%4,扩容后就是%8）
        this.M= newData.length;
        //遍历原数组,进行节点的搬移
        for (int i = 0; i < data.length; i++) {
            if(data[i]!=null){
                //对应链表不为空
                //进行链表遍历
                for(Node x=data[i];x!=null;){
                    //暂存i索引所在链表对应节点的next(暂存后继节点)
                    Node next=x.next;
                    //新数组的索引
                    int newIndex=hash(x.key);
                    //新数组的头插
                    x.next=newData[newIndex];
                    newData[newIndex]=x;
                    //继续进行下一个节点的搬移操作
                    x=next;

                }
            }else{
                //当前数组对应的i索引下没有节点，无需搬移
                continue;//else这步可以不用写
            }
        }
        //最终只需要data=newData就可以切换成新的哈希表
        data=newData;
    }

    /**
     * 删除哈希表中key值对应的节点
     * 返回待删除的键值对对应的value
     * @param key
     * @return
     */
    public int remove(int key){
        int index=hash(key);
        //判断当前链表头节点是否是待删除节点
        Node head= data[index];
        if(head.key==key){
            int val=head.value;
            data[index]=head.next;
            head.next=head=null;//从链表中把这个节点断掉
            size--;
            return val;
        }
        //当前链表头节点不是待删除节点
        Node prev=head;
        while(prev.next!=null){
            if(prev.next.key==key){
                //prev恰好是待删除结点的前驱
                Node cur=prev.next;
                int val=cur.value;
                //删除操作
                prev.next=cur.next;
                cur.next=cur=null;
                size--;
                return val;
            }
            prev=prev.next;
        }
        //走到这此时节点不存在,抛出异常
        throw new NoSuchElementException("no such key!remove error");
    }
    /**
     * 查询key是否存在
     * @param key
     * @return
     */
    public boolean containsKey(int key){
        int index=hash(key);
        //遍历index位置对应的链表，查看是否有节点的key值与查询的key值相等
        for(Node x=data[index];x!=null;x=x.next){
            if(x.key==key){
                return true;
            }
        }
        return false;
    }

    /**
     * 查询val是否存在
     * @param value
     * @return
     */
    public boolean containsValue(int value){
        //遍历整个哈希表
        //数组从左到右遍历
        for (int i = 0; i < size; i++) {
            //依次遍历以数组元素为节点的每个链表
            for(Node x=data[i];x!=null;x=x.next){
                if(x.value==value){
                    return true;
                }
            }
        }
        return false;
    }
}
